<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.6"/>
<title>IVF-HNSW: ivfhnsw::IndexIVF_HNSW Struct Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td style="padding-left: 0.5em;">
   <div id="projectname">IVF-HNSW
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.6 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li class="current"><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="annotated.html"><span>Class&#160;List</span></a></li>
      <li><a href="classes.html"><span>Class&#160;Index</span></a></li>
      <li><a href="hierarchy.html"><span>Class&#160;Hierarchy</span></a></li>
      <li><a href="functions.html"><span>Class&#160;Members</span></a></li>
    </ul>
  </div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Pages</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><b>ivfhnsw</b></li><li class="navelem"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html">IndexIVF_HNSW</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="summary">
<a href="#pub-types">Public Types</a> &#124;
<a href="#pub-methods">Public Member Functions</a> &#124;
<a href="#pub-attribs">Public Attributes</a> &#124;
<a href="#pro-methods">Protected Member Functions</a> &#124;
<a href="#pro-attribs">Protected Attributes</a> &#124;
<a href="structivfhnsw_1_1IndexIVF__HNSW-members.html">List of all members</a>  </div>
  <div class="headertitle">
<div class="title">ivfhnsw::IndexIVF_HNSW Struct Reference</div>  </div>
</div><!--header-->
<div class="contents">

<p><code>#include &lt;<a class="el" href="IndexIVF__HNSW_8h_source.html">IndexIVF_HNSW.h</a>&gt;</code></p>
<div class="dynheader">
Inheritance diagram for ivfhnsw::IndexIVF_HNSW:</div>
<div class="dyncontent">
 <div class="center">
  <img src="structivfhnsw_1_1IndexIVF__HNSW.png" usemap="#ivfhnsw::IndexIVF_HNSW_map" alt=""/>
  <map id="ivfhnsw::IndexIVF_HNSW_map" name="ivfhnsw::IndexIVF_HNSW_map">
<area href="structivfhnsw_1_1IndexIVF__HNSW__Grouping.html" alt="ivfhnsw::IndexIVF_HNSW_Grouping" shape="rect" coords="0,56,214,80"/>
</map>
 </div></div>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-types"></a>
Public Types</h2></td></tr>
<tr class="memitem:a7c6fb7b945eba6a48d28ea36db5809fc"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a7c6fb7b945eba6a48d28ea36db5809fc"></a>
typedef uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a7c6fb7b945eba6a48d28ea36db5809fc">idx_t</a></td></tr>
<tr class="memdesc:a7c6fb7b945eba6a48d28ea36db5809fc"><td class="mdescLeft">&#160;</td><td class="mdescRight">all indices are this type <br/></td></tr>
<tr class="separator:a7c6fb7b945eba6a48d28ea36db5809fc"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr class="memitem:adefe5a46b63461f111c92139c3cdafd6"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="adefe5a46b63461f111c92139c3cdafd6"></a>
&#160;</td><td class="memItemRight" valign="bottom"><b>IndexIVF_HNSW</b> (size_t dim, size_t ncentroids, size_t bytes_per_code, size_t nbits_per_idx, size_t max_group_size=65536)</td></tr>
<tr class="separator:adefe5a46b63461f111c92139c3cdafd6"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ad8520f5a9a46864c038b74116b6d0ba8"><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#ad8520f5a9a46864c038b74116b6d0ba8">build_quantizer</a> (const char *path_data, const char *path_info, const char *path_edges, size_t M=16, size_t efConstruction=500)</td></tr>
<tr class="separator:ad8520f5a9a46864c038b74116b6d0ba8"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a16438e89ea04032d43b7fea4854fdb09"><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a16438e89ea04032d43b7fea4854fdb09">assign</a> (size_t n, const float *x, <a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a7c6fb7b945eba6a48d28ea36db5809fc">idx_t</a> *labels, size_t k=1)</td></tr>
<tr class="separator:a16438e89ea04032d43b7fea4854fdb09"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a276c84ab9e7117ea021a2ff4e11f4a99"><td class="memItemLeft" align="right" valign="top">virtual void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a276c84ab9e7117ea021a2ff4e11f4a99">search</a> (size_t k, const float *x, float *distances, long *labels)</td></tr>
<tr class="separator:a276c84ab9e7117ea021a2ff4e11f4a99"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a750c9093b1fa5adf7d80a9ca6aec5de4"><td class="memItemLeft" align="right" valign="top">virtual void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a750c9093b1fa5adf7d80a9ca6aec5de4">add_batch</a> (size_t n, const float *x, const <a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a7c6fb7b945eba6a48d28ea36db5809fc">idx_t</a> *xids, const <a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a7c6fb7b945eba6a48d28ea36db5809fc">idx_t</a> *precomputed_idx=nullptr)</td></tr>
<tr class="separator:a750c9093b1fa5adf7d80a9ca6aec5de4"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a6774efa5e477a077ec9cf4a6d1f52361"><td class="memItemLeft" align="right" valign="top">virtual void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a6774efa5e477a077ec9cf4a6d1f52361">train_pq</a> (size_t n, const float *x)</td></tr>
<tr class="separator:a6774efa5e477a077ec9cf4a6d1f52361"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ab8deedf4590b4ac38b1c83d4f7d44aca"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="ab8deedf4590b4ac38b1c83d4f7d44aca"></a>
virtual void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#ab8deedf4590b4ac38b1c83d4f7d44aca">write</a> (const char *path)</td></tr>
<tr class="memdesc:ab8deedf4590b4ac38b1c83d4f7d44aca"><td class="mdescLeft">&#160;</td><td class="mdescRight">Write index to the path. <br/></td></tr>
<tr class="separator:ab8deedf4590b4ac38b1c83d4f7d44aca"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:acd6f33b0f7ca53d399f98df18c4a5cc0"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="acd6f33b0f7ca53d399f98df18c4a5cc0"></a>
virtual void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#acd6f33b0f7ca53d399f98df18c4a5cc0">read</a> (const char *path)</td></tr>
<tr class="memdesc:acd6f33b0f7ca53d399f98df18c4a5cc0"><td class="mdescLeft">&#160;</td><td class="mdescRight">Read index from the path. <br/></td></tr>
<tr class="separator:acd6f33b0f7ca53d399f98df18c4a5cc0"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ac5a4b723f412d1a54ddee29db4d6a594"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="ac5a4b723f412d1a54ddee29db4d6a594"></a>
void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#ac5a4b723f412d1a54ddee29db4d6a594">compute_centroid_norms</a> ()</td></tr>
<tr class="memdesc:ac5a4b723f412d1a54ddee29db4d6a594"><td class="mdescLeft">&#160;</td><td class="mdescRight">Compute norms of the HNSW vertices. <br/></td></tr>
<tr class="separator:ac5a4b723f412d1a54ddee29db4d6a594"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a283b84e2daa00165d08e2ed8a1c775ac"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a283b84e2daa00165d08e2ed8a1c775ac"></a>
void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a283b84e2daa00165d08e2ed8a1c775ac">rotate_quantizer</a> ()</td></tr>
<tr class="memdesc:a283b84e2daa00165d08e2ed8a1c775ac"><td class="mdescLeft">&#160;</td><td class="mdescRight">For correct search using OPQ encoding rotate points in the coarse quantizer. <br/></td></tr>
<tr class="separator:a283b84e2daa00165d08e2ed8a1c775ac"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-attribs"></a>
Public Attributes</h2></td></tr>
<tr class="memitem:a609cc185fcb377f9d8bb5a4e5e7d2c4f"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a609cc185fcb377f9d8bb5a4e5e7d2c4f"></a>
size_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a609cc185fcb377f9d8bb5a4e5e7d2c4f">d</a></td></tr>
<tr class="memdesc:a609cc185fcb377f9d8bb5a4e5e7d2c4f"><td class="mdescLeft">&#160;</td><td class="mdescRight">Vector dimension. <br/></td></tr>
<tr class="separator:a609cc185fcb377f9d8bb5a4e5e7d2c4f"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a530ea15e63fa6a6f86cf5feb511c73c3"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a530ea15e63fa6a6f86cf5feb511c73c3"></a>
size_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a530ea15e63fa6a6f86cf5feb511c73c3">nc</a></td></tr>
<tr class="memdesc:a530ea15e63fa6a6f86cf5feb511c73c3"><td class="mdescLeft">&#160;</td><td class="mdescRight">Number of centroids. <br/></td></tr>
<tr class="separator:a530ea15e63fa6a6f86cf5feb511c73c3"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a5dabe1116836baf19e25bc1ea89c565c"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a5dabe1116836baf19e25bc1ea89c565c"></a>
size_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a5dabe1116836baf19e25bc1ea89c565c">code_size</a></td></tr>
<tr class="memdesc:a5dabe1116836baf19e25bc1ea89c565c"><td class="mdescLeft">&#160;</td><td class="mdescRight">Code size per vector in bytes. <br/></td></tr>
<tr class="separator:a5dabe1116836baf19e25bc1ea89c565c"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ac31af605b0da2dd25cd0dbf51f8a4802"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="ac31af605b0da2dd25cd0dbf51f8a4802"></a>
hnswlib::HierarchicalNSW *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#ac31af605b0da2dd25cd0dbf51f8a4802">quantizer</a></td></tr>
<tr class="memdesc:ac31af605b0da2dd25cd0dbf51f8a4802"><td class="mdescLeft">&#160;</td><td class="mdescRight">Quantizer that maps vectors to inverted lists (HNSW [Y.Malkov]) <br/></td></tr>
<tr class="separator:ac31af605b0da2dd25cd0dbf51f8a4802"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:aaf630999dcdc300137ffe8f1e93dde21"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="aaf630999dcdc300137ffe8f1e93dde21"></a>
faiss::ProductQuantizer *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#aaf630999dcdc300137ffe8f1e93dde21">pq</a></td></tr>
<tr class="memdesc:aaf630999dcdc300137ffe8f1e93dde21"><td class="mdescLeft">&#160;</td><td class="mdescRight">Produces the residual codes. <br/></td></tr>
<tr class="separator:aaf630999dcdc300137ffe8f1e93dde21"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:acff5d189392af6d63db5d782df89f79b"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="acff5d189392af6d63db5d782df89f79b"></a>
faiss::ProductQuantizer *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#acff5d189392af6d63db5d782df89f79b">norm_pq</a></td></tr>
<tr class="memdesc:acff5d189392af6d63db5d782df89f79b"><td class="mdescLeft">&#160;</td><td class="mdescRight">Produces the norm codes of reconstructed base vectors. <br/></td></tr>
<tr class="separator:acff5d189392af6d63db5d782df89f79b"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a45f738ebf5e73b87a11983911d54dd8b"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a45f738ebf5e73b87a11983911d54dd8b"></a>
faiss::LinearTransform *&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a45f738ebf5e73b87a11983911d54dd8b">opq_matrix</a></td></tr>
<tr class="memdesc:a45f738ebf5e73b87a11983911d54dd8b"><td class="mdescLeft">&#160;</td><td class="mdescRight">Rotation matrix for OPQ encoding. <br/></td></tr>
<tr class="separator:a45f738ebf5e73b87a11983911d54dd8b"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a9660b70f02a7b529ef7e997a685e1f5e"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a9660b70f02a7b529ef7e997a685e1f5e"></a>
bool&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a9660b70f02a7b529ef7e997a685e1f5e">do_opq</a></td></tr>
<tr class="memdesc:a9660b70f02a7b529ef7e997a685e1f5e"><td class="mdescLeft">&#160;</td><td class="mdescRight">Turn on/off OPQ encoding. <br/></td></tr>
<tr class="separator:a9660b70f02a7b529ef7e997a685e1f5e"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a0be6e0ce24b188401271104857283d48"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a0be6e0ce24b188401271104857283d48"></a>
size_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a0be6e0ce24b188401271104857283d48">nprobe</a></td></tr>
<tr class="memdesc:a0be6e0ce24b188401271104857283d48"><td class="mdescLeft">&#160;</td><td class="mdescRight">Number of probes at search time. <br/></td></tr>
<tr class="separator:a0be6e0ce24b188401271104857283d48"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a23f33c7f1b7707580f61c1e69f1373e1"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a23f33c7f1b7707580f61c1e69f1373e1"></a>
size_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a23f33c7f1b7707580f61c1e69f1373e1">max_codes</a></td></tr>
<tr class="memdesc:a23f33c7f1b7707580f61c1e69f1373e1"><td class="mdescLeft">&#160;</td><td class="mdescRight">Max number of codes to visit to do a query. <br/></td></tr>
<tr class="separator:a23f33c7f1b7707580f61c1e69f1373e1"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ad40193d01d98d4a55847638581d610bb"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="ad40193d01d98d4a55847638581d610bb"></a>
std::vector&lt; std::vector&lt; <a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a7c6fb7b945eba6a48d28ea36db5809fc">idx_t</a> &gt; &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#ad40193d01d98d4a55847638581d610bb">ids</a></td></tr>
<tr class="memdesc:ad40193d01d98d4a55847638581d610bb"><td class="mdescLeft">&#160;</td><td class="mdescRight">Inverted lists for indexes. <br/></td></tr>
<tr class="separator:ad40193d01d98d4a55847638581d610bb"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:ad2ca994b4a3bf65a3fe7d1cf863a0da1"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="ad2ca994b4a3bf65a3fe7d1cf863a0da1"></a>
std::vector&lt; std::vector<br class="typebreak"/>
&lt; uint8_t &gt; &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#ad2ca994b4a3bf65a3fe7d1cf863a0da1">codes</a></td></tr>
<tr class="memdesc:ad2ca994b4a3bf65a3fe7d1cf863a0da1"><td class="mdescLeft">&#160;</td><td class="mdescRight">PQ codes of residuals. <br/></td></tr>
<tr class="separator:ad2ca994b4a3bf65a3fe7d1cf863a0da1"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a569a6cca33552f450f253f4d667b6bc4"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a569a6cca33552f450f253f4d667b6bc4"></a>
std::vector&lt; std::vector<br class="typebreak"/>
&lt; uint8_t &gt; &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a569a6cca33552f450f253f4d667b6bc4">norm_codes</a></td></tr>
<tr class="memdesc:a569a6cca33552f450f253f4d667b6bc4"><td class="mdescLeft">&#160;</td><td class="mdescRight">PQ codes of norms of reconstructed base vectors. <br/></td></tr>
<tr class="separator:a569a6cca33552f450f253f4d667b6bc4"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pro-methods"></a>
Protected Member Functions</h2></td></tr>
<tr class="memitem:abd20f0d5f3a516996267961a578cd584"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="abd20f0d5f3a516996267961a578cd584"></a>
float&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#abd20f0d5f3a516996267961a578cd584">pq_L2sqr</a> (const uint8_t *code)</td></tr>
<tr class="memdesc:abd20f0d5f3a516996267961a578cd584"><td class="mdescLeft">&#160;</td><td class="mdescRight">L2 sqr distance function for PQ codes. <br/></td></tr>
<tr class="separator:abd20f0d5f3a516996267961a578cd584"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pro-attribs"></a>
Protected Attributes</h2></td></tr>
<tr class="memitem:a16ef4d800329fa8a3b7377e21af659f3"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a16ef4d800329fa8a3b7377e21af659f3"></a>
std::vector&lt; float &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a16ef4d800329fa8a3b7377e21af659f3">norms</a></td></tr>
<tr class="memdesc:a16ef4d800329fa8a3b7377e21af659f3"><td class="mdescLeft">&#160;</td><td class="mdescRight">L2 square norms of reconstructed base vectors. <br/></td></tr>
<tr class="separator:a16ef4d800329fa8a3b7377e21af659f3"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a10dd2523ee2de0500e88c256e276f01b"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a10dd2523ee2de0500e88c256e276f01b"></a>
std::vector&lt; float &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a10dd2523ee2de0500e88c256e276f01b">centroid_norms</a></td></tr>
<tr class="memdesc:a10dd2523ee2de0500e88c256e276f01b"><td class="mdescLeft">&#160;</td><td class="mdescRight">L2 square norms of coarse centroids. <br/></td></tr>
<tr class="separator:a10dd2523ee2de0500e88c256e276f01b"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a7143a3df1464f0af998ff7cfdf20b19c"><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a7143a3df1464f0af998ff7cfdf20b19c"></a>
std::vector&lt; float &gt;&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a7143a3df1464f0af998ff7cfdf20b19c">precomputed_table</a></td></tr>
<tr class="memdesc:a7143a3df1464f0af998ff7cfdf20b19c"><td class="mdescLeft">&#160;</td><td class="mdescRight">Size pq.M * pq.ksub. <br/></td></tr>
<tr class="separator:a7143a3df1464f0af998ff7cfdf20b19c"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<div class="textblock"><p>Index based on a inverted file (IVF) with Product Quantizer encoding.</p>
<p>In the inverted file, the quantizer (an HNSW instance) provides a quantization index for each vector to be added. The quantization index maps to a list (aka inverted list or posting list), where the id of the vector is then stored.</p>
<p>At search time, the vector to be searched is also quantized, and only the list corresponding to the quantization index is searched. This speeds up the search by making it non-exhaustive. This can be relaxed using multi-probe search: a few (nprobe) quantization indices are selected and several inverted lists are visited.</p>
<p>Supports HNSW quantizer construction, PQ training, adding vertices, serialization and searching.</p>
<p>Each residual vector is encoded as a product quantizer code.</p>
<p>Currently only asymmetric queries are supported: database-to-database queries are not implemented. </p>
</div><h2 class="groupheader">Member Function Documentation</h2>
<a class="anchor" id="a750c9093b1fa5adf7d80a9ca6aec5de4"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">void ivfhnsw::IndexIVF_HNSW::add_batch </td>
          <td>(</td>
          <td class="paramtype">size_t&#160;</td>
          <td class="paramname"><em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const float *&#160;</td>
          <td class="paramname"><em>x</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const <a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a7c6fb7b945eba6a48d28ea36db5809fc">idx_t</a> *&#160;</td>
          <td class="paramname"><em>xids</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const <a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a7c6fb7b945eba6a48d28ea36db5809fc">idx_t</a> *&#160;</td>
          <td class="paramname"><em>precomputed_idx</em> = <code>nullptr</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">virtual</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>Add n vectors of dimension d to the index.</p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">n</td><td>number of base vectors in a batch </td></tr>
    <tr><td class="paramname">x</td><td>base vectors to add, size n * d </td></tr>
    <tr><td class="paramname">xids</td><td>ids to store for the vectors (size n) </td></tr>
    <tr><td class="paramname">precomputed_idx</td><td>if non-null, assigned idxs to store for the vectors (size n) </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="a16438e89ea04032d43b7fea4854fdb09"></a>
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void ivfhnsw::IndexIVF_HNSW::assign </td>
          <td>(</td>
          <td class="paramtype">size_t&#160;</td>
          <td class="paramname"><em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const float *&#160;</td>
          <td class="paramname"><em>x</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype"><a class="el" href="structivfhnsw_1_1IndexIVF__HNSW.html#a7c6fb7b945eba6a48d28ea36db5809fc">idx_t</a> *&#160;</td>
          <td class="paramname"><em>labels</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">size_t&#160;</td>
          <td class="paramname"><em>k</em> = <code>1</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">
<p>Return the indices of the k HNSW vertices closest to the query x.</p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">n</td><td>number of input vectors </td></tr>
    <tr><td class="paramname">x</td><td>query vectors, size n * d </td></tr>
    <tr><td class="paramname">labels</td><td>output labels of the nearest neighbours, size n * k </td></tr>
    <tr><td class="paramname">k</td><td>number of the closest HNSW vertices to the query x </td></tr>
  </table>
  </dd>
</dl>

</div>
</div>
<a class="anchor" id="ad8520f5a9a46864c038b74116b6d0ba8"></a>
<div class="memitem">
<div class="memproto">
      <table class="memname">
        <tr>
          <td class="memname">void ivfhnsw::IndexIVF_HNSW::build_quantizer </td>
          <td>(</td>
          <td class="paramtype">const char *&#160;</td>
          <td class="paramname"><em>path_data</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const char *&#160;</td>
          <td class="paramname"><em>path_info</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const char *&#160;</td>
          <td class="paramname"><em>path_edges</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">size_t&#160;</td>
          <td class="paramname"><em>M</em> = <code>16</code>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">size_t&#160;</td>
          <td class="paramname"><em>efConstruction</em> = <code>500</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">
<p>Construct from stretch or load the existing quantizer (HNSW) instance</p>
<p>if all files exist, quantizer will be loaded, else HNSW will be constructed </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">path_data</td><td>path to input vectors </td></tr>
    <tr><td class="paramname">path_info</td><td>path to parameters for HNSW </td></tr>
    <tr><td class="paramname">path_edges</td><td>path to edges for HNSW </td></tr>
    <tr><td class="paramname">M</td><td>min number of edges per point, default: 16 </td></tr>
    <tr><td class="paramname">efConstruction</td><td>max number of candidate vertices in queue to observe, default: 500</td></tr>
  </table>
  </dd>
</dl>
<p>There has been removed parallel HNSW construction in order to make internal centroid ids equal to external ones. Construction time is still acceptable: ~5 minutes for 1 million 96-d vectors on Intel Xeon E5-2650 V2 2.60GHz. </p>

</div>
</div>
<a class="anchor" id="a276c84ab9e7117ea021a2ff4e11f4a99"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">void ivfhnsw::IndexIVF_HNSW::search </td>
          <td>(</td>
          <td class="paramtype">size_t&#160;</td>
          <td class="paramname"><em>k</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const float *&#160;</td>
          <td class="paramname"><em>x</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">float *&#160;</td>
          <td class="paramname"><em>distances</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">long *&#160;</td>
          <td class="paramname"><em>labels</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">virtual</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>Query n vectors of dimension d to the index.</p>
<p>Return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.</p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">k</td><td>number of the closest vertices to search </td></tr>
    <tr><td class="paramname">x</td><td>query vectors, size n * d </td></tr>
    <tr><td class="paramname">distances</td><td>output pairwise distances, size n * k </td></tr>
    <tr><td class="paramname">labels</td><td>output labels of the nearest neighbours, size n * k</td></tr>
  </table>
  </dd>
</dl>
<p>Search procedure</p>
<p>During IVF-HNSW-PQ search we compute </p>
<pre class="fragment">d = || x - y_C - y_R ||^2
</pre><p>where x is the query vector, y_C the coarse centroid, y_R the refined PQ centroid. The expression can be decomposed as:</p>
<p>d = || x - y_C ||^2 - || y_C ||^2 + || y_C + y_R ||^2 - 2 * (x|y_R) </p>
<hr/>
<p> term 1 term 2 term 3</p>
<p>We use the following decomposition:</p>
<ul>
<li>term 1 is the distance to the coarse centroid, that is computed during the 1st stage search in the HNSW graph, minus the norm of the coarse centroid</li>
<li>term 2 is the L2 norm of the reconstructed base point, that is computed at construction time, quantized using separately trained product quantizer for such norms and stored along with the residual PQ codes.</li>
<li>term 3 is the classical non-residual distance table.</li>
</ul>
<p>Norms of centroids are precomputed and saved without compression, as their memory consumption is negligible. If it is necessary, the norms can be added to the term 3 and compressed to byte together. We do not think that it will lead to considerable decrease in accuracy.</p>
<p>Since y_R defined by a product quantizer, it is split across sub-vectors and stored separately for each subvector. </p>

<p>Reimplemented in <a class="el" href="structivfhnsw_1_1IndexIVF__HNSW__Grouping.html#a399996617a43e549ee886dcd57424b45">ivfhnsw::IndexIVF_HNSW_Grouping</a>.</p>

</div>
</div>
<a class="anchor" id="a6774efa5e477a077ec9cf4a6d1f52361"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">void ivfhnsw::IndexIVF_HNSW::train_pq </td>
          <td>(</td>
          <td class="paramtype">size_t&#160;</td>
          <td class="paramname"><em>n</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">const float *&#160;</td>
          <td class="paramname"><em>x</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">virtual</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>Train product quantizers</p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">n</td><td>number of training vectors of dimension d </td></tr>
    <tr><td class="paramname">x</td><td>learn vectors, size n * d </td></tr>
  </table>
  </dd>
</dl>

<p>Reimplemented in <a class="el" href="structivfhnsw_1_1IndexIVF__HNSW__Grouping.html#adebace156120602539d25e534887e570">ivfhnsw::IndexIVF_HNSW_Grouping</a>.</p>

</div>
</div>
<hr/>The documentation for this struct was generated from the following files:<ul>
<li><a class="el" href="IndexIVF__HNSW_8h_source.html">IndexIVF_HNSW.h</a></li>
<li>IndexIVF_HNSW.cpp</li>
</ul>
</div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Thu Feb 8 2018 16:55:50 for IVF-HNSW by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.6
</small></address>
</body>
</html>
